package pri.zxx.learndemo.leetcode;

import com.alibaba.fastjson.JSON;
import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.stream.IntStream;

public class Solution {


	public static void main(String[] args) {
		Solution solution = new Solution();
		int[] nums = {1, 2, 3, 4, 5};
		System.out.println(solution.removeElement(nums, 3));
		int[] num2 = {0, 0, 0, 1, 1, 1, 2, 3, 4, 5, 5};
		int[] num3 = {0, 0, 0, 1, 1, 1, 2, 3, 4, 5, 5};
		System.out.println(solution.removeDuplicates(num2));
		System.out.println(solution.removeDuplicates2(num3));
	}

	public int removeElement(int[] nums, int val) {
		int n = nums.length;
		int left = 0;
		for (int right = 0; right < n; right++) {
			if (nums[right] != val) {
				nums[left] = nums[right];
				left++;
			}
		}
		int[] ints = Arrays.copyOfRange(nums, 0, left);

		System.out.println(JSON.toJSONString(ints));
		return left;
	}

	public int removeDuplicates(int[] nums) {
		int len = nums.length;
		int left = 0;
		for (int right = 1; right < len; ) {
			if (nums[left] != nums[right]) {
				nums[left + 1] = nums[right];
				left++;
			}
			right++;
		}
		System.out.println(JSON.toJSONString(Arrays.copyOfRange(nums, 0, left + 1)));

		return len - (left + 1);
	}

	public int removeDuplicates2(int[] nums) {
		int len = nums.length;
		int left = 2;
		for (int right = 2; right < len; ) {
			if (nums[left - 2] != nums[right]) {
				nums[left] = nums[right];
				left++;
			}
			right++;

		}
		System.out.println(JSON.toJSONString(Arrays.copyOfRange(nums, 0, left + 1)));
		return len - (left + 1);
//		System.out.println(JSON.toJSONString(Arrays.copyOfRange(nums, 0, left + 1)));
	}


	@Test
	public void moveZeroes() {
		int[] nums = {1, 0, 2, 3, 4, 0, 6, 7, 0};
		int idx = 0;
		for (int num : nums) {
			if (num != 0) {
				nums[idx] = num;
				idx++;
			}
		}
		while (idx < nums.length) {
			nums[idx] = 0;
			idx++;
		}
		System.out.println(JSON.toJSONString(nums));
	}

	@Test
	public void sortBubble() {
//		int[] array = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1};
		int[] array = {1, 2, 3, 4, 5, 6};
		boolean exchange = false;
		for (int i = 0; i < array.length - 1; i++) {
			for (int j = 0; j < array.length - i - 1; j++) {
				if (array[j] > array[j + 1]) {
					swap(array, j, j + 1);
					exchange = true;
				}
				System.out.println(JSON.toJSONString(array));
			}
			if (!exchange) {
				break;
			}
		}
	}

	@Test
	public void sortBubble2() {
//		int[] array = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1};
		int[] array = {1, 2, 3, 4, 5, 6};

		bubble(array, array.length - 1);
	}

	private static void bubble(int[] array, int j) {
		if (j == 0) {
			return;
		}
		int x = 0;
		for (int i = 0; i < j; i++) {
			if (array[i] > array[i + 1]) {
				swap(array, i, i + 1);
				x = i;
			}
			System.out.println(JSON.toJSONString(array));
		}
		bubble(array, x);
	}

	@Test
	public void sortSelect() {
		int[] array = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1};
		for (int i = 0; i < array.length - 1; i++) {
			int minIndex = i;
			for (int j = i + 1; j < array.length; j++) {
				if (array[minIndex] > array[j]) {
					minIndex = j;
				}
			}
			if (minIndex != i) {
				swap(array, minIndex, i);
			}
			System.out.println(JSON.toJSONString(array));
		}
	}

	@Test
	public void sortInsert() {
		int[] array = {9, 2, 3, 2, 3, 1, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1};
		//有序位置默认左边第一个。
		for (int i = 1; i < array.length; i++) {
			int index = i; //无序起始位置 第2个元素往右为无序
			while (index > 0 && array[index] < array[index - 1]) {
				swap(array, index, index - 1);
				index--;
				System.out.println(JSON.toJSONString(array));
			}
		}
	}

	@Test
	public void sortInsert2() {
		int[] array = {9, 2, 3, 2, 3, 1, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1};
		System.out.println(JSON.toJSONString(array));

		insert(array, 1);
	}

	private static void insert(int[] array, int unOrderIndex) {
		if (unOrderIndex == array.length) {
			return;
		}

		int unOrder = array[unOrderIndex];
		int insertIndex = unOrderIndex - 1;
		while (insertIndex >= 0 && array[insertIndex] > unOrder) {
			array[insertIndex + 1] = array[insertIndex];
			insertIndex--;
		}
		if (insertIndex + 1 != unOrderIndex) {
			array[insertIndex + 1] = unOrder;
		}
		System.out.println(JSON.toJSONString(array));

		insert(array, unOrderIndex + 1);
	}

	@Test
	public void sortShell() {
		int[] array = {9, 2, 3, 2, 3, 1, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1};
		int gap = array.length / 2;
		while (gap > 0) {
			for (int j = gap; j < array.length; j++) {
				for (int k = j - gap; k >= 0; k -= gap) {
					if (array[k] > array[k + gap]) {
						swap(array, k, k + gap);
						System.out.println(JSON.toJSONString(array));
					} else {
						break;
					}
				}
			}
			System.out.println("----");
			gap = gap / 2;
		}
	}

	@Test
	public void sortMegre() {
		int[] array = {9, 2, 3, 2, 3, 1, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1};

	}

	@Test
	public void sortQuick() {
		int[] array = {9, 2, 3, 2, 3, 1, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1};


		sortQuick(array, 0, array.length - 1);

		System.out.println(JSON.toJSONString(array));

	}

	public static void sortQuick(int[] arr, int start, int end) {

		if (end <= start) {
			return;
		}

		int l = start, r = end, b = arr[start];
		while (l < r) {
			while (l < r && arr[r] > b) {
				r--;
			}
			if (l < r) {
				arr[l++] = arr[r];
			}
			while (l < r && arr[l] < b) {
				l++;
			}
			if (l < r) {
				arr[r--] = arr[l];
			}
		}
		arr[l] = b;
		sortQuick(arr, start, l - 1);
		sortQuick(arr, l + 1, end);
	}

	public static void swap(int[] array, int i, int j) {
		int tem = array[i];
		array[i] = array[j];
		array[j] = tem;
	}

	@Test
	public void binSearchRecursion() {
		int[] array = new int[99];
		IntStream.range(0, 99).forEach(value -> array[value] = value + 1);
		int i = binSearchFind(array, 100, 0, array.length - 1);
		System.out.println(i);
	}

	private static int binSearchFind(int[] arr, int target, int l, int r) {
		if (l > r) {
			return -1;
		}
		int mid = (l + r) >>> 1;
		if (arr[mid] < target) {
			return binSearchFind(arr, target, mid + 1, r);
		} else if (arr[mid] > target) {
			return binSearchFind(arr, target, l, mid - 1);
		} else {
			return mid;
		}
	}

	@Test
	public void binSearch() {
		int[] array = new int[99];
		IntStream.range(0, 99).forEach(value -> array[value] = value + 1);
		System.out.println(JSON.toJSONString(array));

		int target = 32;
		int start = 0, end = array.length;

		if (array[start] >= target || array[end - 1] <= target) {
			System.out.println(-1);
		}

		while (start < end) {
			int mid = (end + start) >>> 1;
			if (array[mid] > target) {
				end = mid;
			} else if (array[mid] < target) {
				start = mid + 1;
			} else {
				System.out.println("index:" + mid);
				System.out.println("array[" + mid + "] = " + array[mid]);
				break;
			}
		}
	}

	/**
	 * 合并两个有序数组
	 */
	@Test
	public void merge() {

		int[] arr1 = new int[]{1, 2, 4, 8};
		int[] arr2 = new int[]{2, 3, 5, 6, 9};

		int[] mergeArr = new int[arr1.length + arr2.length];

		int i = 0, j = 0;
		for (int k = 0; k < mergeArr.length; k++) {

			if (i == arr1.length) {
				mergeArr[k] = arr2[j++];
				continue;
			}
			if (j == arr2.length) {
				//可优化 System.arrayCopy
				mergeArr[k] = arr1[i++];
				continue;
			}

			if (arr1[i] < arr2[j]) {
				mergeArr[k] = arr1[i];
				i++;
			} else {
				mergeArr[k] = arr2[j];
				j++;
			}
		}
		System.out.println(JSON.toJSONString(mergeArr));
	}

}
